package com.mrl.linkedlist;

import java.util.Stack;

/**
 * 使用单向环形链表解决约瑟夫问题
 * @author 正义桑
 * @version 1.0
 */
public class Josepfu {
    public static void main(String[] args) {
        CircleSingleLinkedList list = new CircleSingleLinkedList();
        list.calcJosepfu(1,2,10);
    }
}

class CircleSingleLinkedList {
    private Boy first;

    /**
     * 向链表中添加小孩
     * @param num 添加小孩的数量
     */
    public void addBoy(int num) {
        if (num < 2) {
            System.out.println("添加小孩的数目不合法!");
            return;
        }
        Boy curBoy = null;
        for (int i = 1;i <= num;i++) {
            if (i == 1) {
                curBoy = new Boy(i);
                first = curBoy;
            } else {
                curBoy.setNext(new Boy(i));
                curBoy = curBoy.getNext();
            }
            curBoy.setNext(first);
        }
    }

    /**
     * 列出链表中存在的数据
     */
    public void list() {
        if (first == null) {
            System.out.println("链表为空");
            return;
        }
        Boy curBoy = first;
        do {
            System.out.printf("%d \n", curBoy.getId());
            curBoy = curBoy.getNext();
        } while (curBoy != first);
    }

    public void calcJosepfu(int n, int m, int nums) {
        if (n < 1 || m > nums || nums < 2) {
            System.out.println("输入数据不合法!");
            return;
        }
        addBoy(nums);
        // 将tmp指针移动到first前一个位置
        Boy tmp = first;
        while (tmp.getNext() != first) {
            tmp = tmp.getNext();
        }
        // 初始化first指针位置
        for (int i = 0;i < n - 1;i++) {
            first = first.getNext();
            tmp = tmp.getNext();
        }
        // 开始解题
        while (first.getNext() != first) {
            // 移动m次
            for (int i = 0;i < m - 1;i++) {
                first = first.getNext();
                tmp = tmp.getNext();
            }
            // 取出first
            System.out.printf("取出编号为%d的小孩", first.getId());
            first = first.getNext();
            tmp.setNext(first);
        }
    }
}

class Boy {
    private int id;
    private Boy next;

    public Boy(int id) {
        this.id = id;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }
}
